package com.data_structure_algorithm.sort;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {

        int[] arr = {1, 9, 86, 4, 1, 2, 5, 7, 54, 2, 55, 2, 5, 83, 22, -1};
        sort4(arr, 0, arr.length - 1);

        System.out.println(Arrays.toString(arr));

      /*  int[] arrs = new int[20000000];
        for (int i = 0; i < 20000000; i++) {
            arrs[i] = (int) (Math.random() * 80000000);
        }
        String dateStart = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());
        System.out.println(dateStart);
        sort3(arrs, 0, arrs.length - 1);
        String dateEnd = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());

        System.out.println(dateEnd);*/
    }

    private static void sort4(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }

        //思路：每次将数组最左侧作为base，
        int base = arr[left];
        int i = left;
        int j = right;
        while (i != j) {
            //从数组右侧依次和base比较，找比base小的
            while (arr[j] >= base && i < j) {
                j--;
            }
            //从数组左侧依次和base比较，找比base大的
            while (arr[i] <= base && i < j) {
                i++;
            }

            //交换位置
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }


        //将base和当前重合位置交换
        arr[left] = arr[i];
        arr[i] = base;
        //递归
        //分两边
        sort4(arr, left, i - 1);

        sort4(arr, i + 1, right);

    }

    private static void sort3(int[] arr, int left, int right) {
        int count = 0;
        if (left > right) return;

        int base = arr[left];

        int i = left;

        int j = right;

        while (i != j) {
            //右-->左
            while (i < j && arr[j] >= base) {
                j--;
            }

            while (i < j && arr[i] <= base) {
                i++;
            }

            //ij互换位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        //结束，base和i/j互换位置，1轮完成
        arr[left] = arr[i];
        arr[i] = base;

    /*    System.out.println(left);
        System.out.println(right);*/
        //System.out.println("第" + (++count) + "轮调用");

        //继续分化调用
        sort3(arr, left, i - 1);
        sort3(arr, i + 1, right);
    }


    private static void sort(int[] arr, int left, int right) {

        if (left > right) return;

        //找出基准数，其他数据分别和基准数比较
        int base = arr[left];
        //定义变量保存索引
        int i = left;
        int j = right;
        //以最左边的数为基准数，而后从两边检索


        while (i != j) {
            //从数组右侧J向左检索比基准数小的
            while (arr[j] >= base && i < j) {
                j--;
            }
            //反之左侧I检索比基准数大的
            while (arr[i] <= base && i < j) {
                i++;
            }

            //走到这里说明停止了
            //交换j 和i 的位置
            int temp;
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //直到J==I，重合了，将当前停下数据的位置和基准数交换，一轮结束，基准数左边都比其小，右边都比其大
        //交换基准数和停止的位置数值
        arr[left] = arr[i];
        arr[i] = base;//base提前取出来了

        //继续排序
        sort(arr, left, i - 1);
        sort(arr, j + 1, right);
    }


    private static void sort2(int[] arr, int left, int right) {
        if (left > right) {
            return;
        }

        //确定基准数
        int base = arr[left];

        //确定索引
        int i = left;
        int j = right;

        while (i != j) {

            while (i < j && arr[j] >= base) {
                j--;
            }

            while (i < j && arr[i] <= base) {
                i++;
            }
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //重合
        arr[left] = arr[i];
        arr[i] = base;

        sort2(arr, left, i - 1);
        sort2(arr, j + 1, right);
    }
}
